Network computing has grown at a phenomenal rate over the last decade. In a network computing environment, the user has access to the computing power of multiple computers coupled to the network. Sun Microsystems Inc., a leader in network computing, has even devised a marketing campaign around the slogan "The Network Is the Computer".TM. to emphasize the commercial success of this growing segment of the computing market. (The Network Is the Computer, Sun, the Sun logo, Sun Microsystems, Solaris, Ultra and Java are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and in other countries. All SPARC trademarks are used under license and are trademarks or registered trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc. UNIX is a registered trademark in the United States and other countries exclusively licensed through X/Open Company, Ltd.) Recently, this slogan has become reality as many millions of users have tapped the computing resources available from the thousands of computers available on the Internet and the World Wide Web.
The wide spread growth of the Internet and the World Wide Web can be attributed to the use of standard networking protocols and routers which couple different networks together. A typical network protocol, such as TCP/IP, includes an application layer, a process layer, a host-to-host protocol layer (TCP/UDP), an internet protocol layer (IP), a network protocol layer and a physical layer. Often, routers are used to convert information from different networks at the physical layer and the network layer. In particular, the different physical layers have a corresponding media access layer (MAC) which specifies, among other things, the maximum transmission unit (MTU) which can be transmitted over the physical medium. Generally, the MTU is defined as a maximum number of transmission units any network segment is capable of transmitting. As part of the conversion process, routers may be required to fragment packets traveling from a network with a large MTU into smaller segments on a network with a smaller MTU.
For example, the Internet is a heterogeneous IP network which couples together different physical media and corresponding MAC layers which include Ethernet, IEEE 802.3 (CSMA/CD), IEEE 802.4 (Token ring), PPP/SLIP (dial-up), T-1, T-3, and air interfaces for wireless technologies such as CDMA, TDMA, AMPS, and GSM. At the higher layers, these different networks share host-to-host protocols such as TCP, UDP and application protocols such as mail, finger, and ftp. Even across different networks, these higher layer protocols remain compatible. However, at the network and MAC layers these different networks have a wide variety of MTU values and generate datagram segments which are often incompatible in size. As of November 1990, common MTUs (in bytes) associated with various data links on the Internet include: 65535 Theoretical Maximum (RFC 791); 65535 Hyperchannel (RFC 1044); 17914 IBM Token Ring (RFC 791); 8166 IEEE 802.4 (RFC 1042); 4464 IEEE 802.5 (4 Mb max) (RFC 1042); 4352 FDDI (revised) (RFC 1188); 2048-4352 Wideband Network (RFC 1188); 2002 IEEE 802.5 (4 Mb recommended) (RFC 1042); 1536-2002 Exp. Ethernet Nets (RFC 895); 1500 Ethernet Networks (RFC 894); 1500 Point-to-Point (default) (RFC 1134); 1492 IEEE 802.3 (RFC 1042); 1006-1492 SLIP (RFC 1055); 1006 ARPANET (BBN 1822); 576-1006 X.25 Networks (RFC 877); 544 DEC IP Portal; 512 Netbios (RFC 1088); 508 IEEE 802/Source-Rt Bridge; (RFC 1042); 508 ARCNET (RFC 1051); 296-508 Point-to-Point (low delay) (RFC 1144); 68 Official minimum MTU. The RFC or request for comment number can be used to locate the corresponding document published by the Internet Engineering Task Force (IETF).
MTU incompatibility arises because datagrams are packets of information sent over a connectionless network. In other words, there is no single connection between a source and a destination node in which a packet of information is restricted to travel. Instead, each packet typically travels over a different path of a heterogeneous network to arrive at the destination node. Consequently, each datagram may be fragmented by different amounts to conform to the MTU of each intermediary network. For example, datagram segments transmitted from an Ethernet network typically are 1500 bytes long and must be split into several smaller datagram segments to travel over an X.25 (MTU 576) or Netbios (MTU 512) physical network layer. Thus, the routers used in the Internet spend a great deal of processor cycles requesting smaller datagram segment sizes or fragmenting these segments into smaller segments compatible on other portions of the network.
Unfortunately, achieving network interoperability by successive fragmentation reduces network performance because of increased data processing and transmission overhead. Initially, fragmentation drains the processing power of routers as the large segments are reduced into smaller and smaller segments for transmission over networks having physical network layer's with successively smaller MTUs. On the receiving end, the destination host expends more processing power and resources to buffer the enlarged pool of segments and to reassemble the enlarged pool of segments into the original message. Moreover, sending additional packets over the network increases the amount of packet header information transmitted and thus reduces the effective network bandwidth.
Controlling fragmentation is particularly challenging on a connectionless network because, as discussed above, each segment may be transmitted over a different route. Some segments, known as datagrams on a connectionless network, may be transmitted over a route with a large MTU and not require fragmentation. However, if a segment of the network fails or is incorrectly reconfigured, the network topology will change and subsequent segments may be sent over a route with a smaller MTU and requiring extensive fragmentation. Complex routings make it difficult for the source host to select the appropriate datagram size which will minimize the fragmentation. For example, assume a primary route used over the Internet includes an IEEE 802.4 network having a an MTU of 8166 bytes and a secondary route includes a an X.25 network having a much smaller MTU of 576 bytes. To minimize the number of packets transmitted, assume that each datagram is based on the larger MTU of the two routes and contains 8166 bytes. Initially, datagrams transmitted over the primary route do not require any fragmentation. However, when the primary route becomes unavailable or busy the network topology changes and the secondary route, with the smaller MTU of 576 bytes, takes the traffic. Consequently, the routers fragment each of the remaining datagrams and transmits them over the Internet which, as previously discussed above, reduces the effective network bandwidth. Clearly, selecting a datagram size which minimizes fragmentation on a connectionless network is a difficult task.
Current techniques for selecting a datagram size which reduces overall fragmentation yet optimizes the network bandwidth have had limited success. A common practice assumes the data is going to be transmitted over a local network and generates datagrams based on the local network MTU. Unfortunately, this technique will result in fragmentation and increased overhead if the datagrams are transmitted over remote networks having an MTU smaller than the local network MTU size. For example, assume a data transmission is sent from one Ethernet to another Ethernet coupled together by router devices and an X.25 network. Further assume the MTU of the Ethernet networks are 1500 bytes and the MTU of the X.25 network between the two Ethernet networks is 576 bytes. Accordingly, datagrams generated using this first technique will be fragmented into two 576 byte datagrams and one 348 byte datagram to cross over the X.25 network. This technique typically does not reduce fragmentation unless the datagram stays on the local network.
Another technique, determines how large the datagrams should be based upon the lesser of 576 bytes or the first-hop MTU when sending to any network that is not connected to the same local network or subnet as the source host. In this context, a hop count measures the distance travelled on a network by counting the number of routers, switches, or bridges traversed by a given packet. A hop count of M associated with a packet indicates that the packet has traversed approximately M different networks. As a corollary, the first-hop MTU of a network is the MTU of a network exactly one hop away from the transmitting network. Unfortunately, this technique of selecting an MTU typically generates smaller datagrams than necessary and results in network inefficiencies and wastes available network bandwidth. Further, this may also result in fragmentation when a datagram traverses a network with an MTU smaller than 576.
A third technique determines the size of the datagrams based upon the path MTU (PMTU) of a route between a source node and a destination node on a network. A PMTU discovery technique as applied to an IP network is documented in RFC 1191 entitled "Path MTU Discovery" written by Jeffrey Mogul and Steve Deering and published in conjunction with the Internet Engineering Task Force (IETF). Briefly, this technique uses a "Don't Fragment" (DF) bit in the IP header to dynamically discover the PMTU of an arbitrary network path. At first, the source host assumes the PMTU is the first-hop MTU and sends all the datagrams on that path with the DF bit set. If these datagrams are too large to be forwarded without fragmentation by some router along the arbitrary network path, the offended router will drop the oversized datagrams and return an Internet Control Message Protocol (ICMP) Destination Unreachable message to the source node with a special code indicating "fragmentation needed and DF bit set". In response, the source node repeats the above process using smaller and smaller datagrams until the datagrams are delivered without fragmentation. Unfortunately, each successive datagram transmitted over a connectionless network such as the Internet can traverse a different route and have a different PMTU value than the previous datagram transmitted over the same network. Thus, even systems using Path MTU Discovery will fail to reduce fragmentation and thereby decrease the effective bandwidth of the network when packet retransmissions become excessive.
Consequently, what is needed is a method and system for generating packets used in a network which reduces the amount of fragmentation and increases the effective network bandwidth associated with transmitting packets over a network.